package 图.树;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 对一些常见的 二叉树的 方法 和 特性 进行总结 ！ ：
 * 
 * 满二叉树
 * 		nodes = 2 ^ h - 1 
 * 		h 树的高度, nodes 图.树 的 总的节点数
 * 		也是应用   树形 dp
 * 完全二叉树
 * 		这个好像有点难搞!		
 * 		判断起来还是挺复杂的!
 * 搜索二叉树
 * 		直接中序 遍历收集节点 ,然后判断是否有序!
 * 		直接在递归的 时候 ,就进行 有序的 判断
 * 平衡二叉树
 * 		树形 dp 可以解决
 * 平衡二叉搜索树
 *		这个可能比较难搞!
 
 
 *所以可以 出的 question 应运而生!
 *判断 ,一个 BinaryTree 是否 上面的 各 二叉树!
 * 
 * 
 * 
 * 
 *给定一个二叉树(普通的二叉树)(二叉树中的值重不重复其实 都可以) , && 一个 值   aim ,如果 在二叉树中找到 aim ,返回true,否则 false!
 *		这个题 的 解题 思想可以 去 思考一下! 
 *		本质上 还是应用了  树形   dp 的思想 ! 
 *		把左子树 返回 的结果 ,和 右子树 返回的 结果, 进行 一定 需求 处理, 然后返回给上一层!
 *
 *
 *
 *搜索二叉树 中删除 指定 aim 的节点 ,分析的逻辑 非常复杂!
 * @author I adore you
 */
public class Note {
	
	
	
	
	/**
	 * 搜索二叉树 中删除 值 为    aim 的节点;
	 */
	
	public TreeNode deleteAimNode(TreeNode root,int aim) {
		if(root.val == aim) {
			if(root.right != null) {
				TreeNode node = getRightNodeLeftest(root.right,root);
				root.val = node.val;
//				node.left = root.left;
//				node.right = root.right;
//				root = null;
//				return node;
				return root;
			}
			if(root.left == null)
				return null;
			return root.left;			
		}
		process(root,root,aim);
		return  root;
			
	}
	
	public void process(TreeNode node,TreeNode father,int aim) {
		if(node == null)
			return ;
		if(node.val == aim) {
			// 右节点 不为 null 
			if(node.right != null) {
				node.val = getRightNodeLeftest(node,father).val;
				return;
			}
			// 左 右 节点 为  null
			if(node.left == null) {
				if(isRightOrLeftNode(node,father))
					father.left = null;
				else 
					father.right = null;
			}
			//  右节点 为 null ,左节点  不为 null
			if(isRightOrLeftNode(node,father))
				father.left = node.left;
			else
				father.right = node.left;
		}
		if(node.val > aim)
			process(node.left,node,aim);
		if(node.val < aim)
			process(node.right,node,aim);
		
	}
	
	/**
	 * 这个 father 参数  好像是无法 缺少!
	 * @param node
	 * @param father
	 * @return
	 */
	public TreeNode getRightNodeLeftest(TreeNode node,TreeNode father) {
		if(node.left == null) {
			if(isRightOrLeftNode(father,node))
				father.left = null;
			else
				father.right = null;
			return node;
		}
		return getRightNodeLeftest(node.left,node);
	}
	/**
	 *  返回结果 true = 左子节点
	 *  返回结果false = 右子节点
	 * @return
	 */
	public boolean isRightOrLeftNode(TreeNode father,TreeNode children) {
		return father.left == children ? true : false;
	}
	
	
	
	
	/**
	 * 在二叉树中 找一个 , 值为  aim  是否存在
	 */
	
	public boolean isExist(TreeNode node ,int aim) {
		if(node == null)
			return false;
		if(node.val == aim)
			return true;
		// 这里的  || 就真的 很妙 , 其实本质还是树形  dp 的思想
		return isExist(node.left,aim) || isExist(node.right,aim);
		
	}

	/**
	 * 判断是否为:
	 * 平衡二叉树
	 */
	public boolean isBBT(TreeNode node) {
		if(node == null)
			return false;
		return  isBanlanceTree(node)[0] == 1;
		// 上面的额 代码   细不细节!
	}
	
	/**
	 * 这里的 返回 结果当然 也可以声明成 一个 
	 * 内部   class, 
	 * 也可以 用 数组 int []  ans [0]: 可以 用数值 来表示 bool 值 : ans[0] = 0 = false, ans[0] = 1 =  true
	 * ans [1]  表示 子树的 height   
	 */
	public int [] isBanlanceTree(TreeNode node) {
		if(node == null)
			return new int [] {0, 0};
		int leftData [] = isBanlanceTree(node.left);
		int rightData [] = isBanlanceTree(node.right);
		
		boolean flag = leftData[0] == 1 && rightData[0] == 1 && Math.abs(leftData[1] - rightData[1]) <= 1;
		int height = Math.max(leftData[1], rightData[1]) + 1;
		return new int [] {flag ? 1: 0,height};
	}
	
	
	/**
	 * 这个 函数是对结果进行处理判断的代码
	 */
	public boolean solution(TreeNode node) {
		if(node == null)
			return false;
		int ans [] = isFullBianryTree(node);
		return ans[0] == (1 << ans[1]) - 1;
	}
	
	/**
	 * int [] ans,  ans[0] : 表示 nodes, ans[1] 表示 height
	 * 下面是递归 过程 代码!
	 */
	public int [] isFullBianryTree(TreeNode node) {
		if(node == null)
			return new int [] {0,0};
//		int ans [] = new int [2];
		int [] leftData = isFullBianryTree(node.left);
		int [] rightData = isFullBianryTree(node.right);
		
		int nodes = leftData[0] + rightData[0] + 1;
		int height = Math.max(leftData[1],rightData[1]) + 1;
		return new int [] {nodes,height};		
	}
	
	
	
	
	
	
	
	/**
	 * 二 叉树的 层序遍历
	 */
	void bfs(TreeNode root) {
		Deque<TreeNode> queue = new ArrayDeque<>();
		queue.addLast(root);
		while(!queue.isEmpty()) {
			int size = queue.size();
			while(size-- > 0) {
				TreeNode temp = queue.poll();
				System.out.println(temp);
				if(temp.left != null)
					queue.addLast(temp.left);
				if(temp.right != null)
					queue.addLast(temp.right);
			}
		}
		
	}
	
	
	//   二叉树的 递归 序
	void recursion(TreeNode node) {
		if(node == null)
			return ;
		// 这里是 前序
		recursion(node.left);
		
		// 这里是 中序
		recursion(node.right);
		// 这里是 后序
	}
	
	
	
	/**
	 * leetcode 111  求二叉树的最小深度 ,还挺有 意思的 
	 * 求二叉树 的 height
	 * 这个 拆开 来讲 就是 一个简单的 树形 dp
	 * int leftData  = height(node.left);
	 * int rightData = height(node.right);
	 * 
	 * 左子树  返回结果,
	 * 右子树返回结果
	 * 对左右  子树 返回的结 果 进行处理, 并向上一级 进行返回!
	 */
	int height(TreeNode node) {                      
		if(node == null)
			return 0;
		return Math.max(height(node.left), height(node.right)) + 1;
	}
	
	
	
	 public static TreeNode stringToTreeNode(String input) {
	        input = input.trim();
	        input = input.substring(1, input.length() - 1);
	        if (input.length() == 0) {
	            return null;
	        }
	    
	        String[] parts = input.split(",");
	        String item = parts[0];
	        TreeNode root = new TreeNode(Integer.parseInt(item));
	        Queue<TreeNode> nodeQueue = new LinkedList<>();
	        nodeQueue.add(root);
	    
	        int index = 1;
	        while(!nodeQueue.isEmpty()) {
	            TreeNode node = nodeQueue.remove();
	    
	            if (index == parts.length) {
	                break;
	            }
	    
	            item = parts[index++];
	            item = item.trim();
	            if (!item.equals("null")) {
	                int leftNumber = Integer.parseInt(item);
	                node.left = new TreeNode(leftNumber);
	                nodeQueue.add(node.left);
	            }
	    
	            if (index == parts.length) {
	                break;
	            }
	    
	            item = parts[index++];
	            item = item.trim();
	            if (!item.equals("null")) {
	                int rightNumber = Integer.parseInt(item);
	                node.right = new TreeNode(rightNumber);
	                nodeQueue.add(node.right);
	            }
	        }
	        return root;
	    }
	 
	 public static void main(String []args) {
		 /**
		  * 既可以用作 stack ,又可以用作 队列 queue
		  */
		 Deque<Integer> test = new ArrayDeque<>();
		 test.add(1);
		 test.add(5);
		 test.add(7);
		 test.add(8);
		 System.out.println(test);
		 System.out.println(test.pop());
		 System.out.println(test.pollLast());
		 
		 System.out.println((1 << 4) - 1);
		 
	 }
	 /**
	 
	    public static void main(String[] args) throws IOException {
	        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	        String line;
	        while ((line = in.readLine()) != null) {
	            TreeNode root = stringToTreeNode(line);
	            
	            int ret = 0;
	            // 调用返回  的  结果类
//	            int ret = new Solution().minDepth(root);
	            
	            String out = String.valueOf(ret);
	            
	            System.out.print(out);
	        }
	    }
	 
	 */
	
}

/**
 * 树的 节点
 */
//class TreeNode{
//	int val;
//	TreeNode left;
//	TreeNode right;
//}
